FIG. 21 shows a basic structure for band splitting by wavelet transform and synthesis by inverse wavelet transform. An input here is a one-dimensional signal x[i].
Referring to FIG. 21, a wavelet transform unit 2 splits the one-dimensional signal x[i] entering an input terminal 1 into signals of plural frequency bands (sub-band signals). An inverse wavelet transform unit 4 synthesizes the signals xa'[j], xb'[j], xc'[j], . . . , split into sub-bands, in order to restore the input signal x[j]. A signal processor 3 processes data split into plural frequency bands in a pre-set manner. For example, if the signal processor 3 executes the encoding, it executes quantization, variable length encoding, transmission, variable length decoding and dequantization.
That is, in the wavelet transform unit 2, each of analysis filters 11, 12, 13, . . . fed with the one-dimensional signal x[i] splits the one-dimensional signal x[i] entering the input terminal 1 into plural frequency bands. The analysis by these analysis filters 11, 12, 13, . . . gives data strings of respective frequency bands xa[i], xb[i], xc[i], . . . , which are sent to respective downsampling units 21, 22, 23, . . . . These downsampling units 21, 22, 23 execute downsampling of saving data of the data strings of respective frequency bands xa[i], xb[i], xc[i], . . . associated with the sampling intervals Dt (t=1, 2, 3, . . . ) while thinning out the remaining data. The data xa'[i], xb'[i], xc'[i], . . . of the respective frequency bands, obtained on downsampling by the downsampling units 21, 22, 23, . . . are sent to the signal processor 3 for predetermined signal processing.
The data strings of the respective frequency bands, processed in a predetermined manner by the signal processor 3, are sent to the inverse wavelet transform unit 4 which then sends the input data strings of the input respective frequency bands to upsampling units 41, 42, 43, . . . associated with the respective frequency bands. These upsampling units 41, 42, 43, . . . pad the interval between two temporally neighboring data with a suitable number of zeros. The number of inserted zeros is equal to the number of samples (Dt-1) of data thinned out by the downsampling units 21, 22, 23, . . . associated with these upsampling units 41, 42, 43, . . . . This substantially restores the data strings xa[i], xb[i], xc[i], . . . of the respective frequency bands. The data strings xa[i], xb[i], xc[i], . . . of the respective frequency bands, resulting from these upsampling operations, are sent to associated synthesis filters 51, 52, 53, . These synthesis filters 51, 52, 53, . . . perform interpolation processing on the supplied data strings xa[i], xb[i], xc[i], . . .. Output data of the synthesis filters 51, 52, 53, . . . are sent to an adder 6 which then sums these output data to restore the one-dimensional signal x[i] as a synthesized output signal X"[i] which is outputted at an output terminal 5.
An embodiment for splitting the input one-dimensional signal into two sub-bands is explained specifically. Meanwhile, there are provided two each of the analysis filters and downsampling units of the wavelet transform unit and two each of the upsampling units and synthesis filters of the inverse wavelet transform unit.
In this case, the two analysis filters 11, 12 of the wavelet transform unit are a low-pass filter and a high-pass filter. The two analysis filters, that is the analysis low-pass and high-pass filters 11, 12, band-split the input one-dimensional signal x[i] into a data string XL[i] of the low frequency band and a data string XH[i] of the high frequency band, respectively. Also, the downsampling units 21, 22 decimate the band-split data strings XL[i] and XH[i] every other ample in order to find down-sampled data strings XL[j] and XH[j] of the two frequency bands, as shown by the following equations (1) and (2): EQU XL[j]=XL[i], where j=i/2 . . . (1) EQU XH[j]=XH[i], where j=i/2 . . . (2)
In the inverse wavelet transform unit, the signal-processed data strings of the two frequency bands have their sample intervals expanded by two by upsampling units 41, 42. In addition, zero-valued samples are inserted at the center positions of the data strings of the two bands. This upsampling operation may be represented by the following equations (3) and (4): ##EQU1##
The data strings XL[i], XH[i] of the respective frequency bands, obtained on upsampling by the upsampling units 41, 42, are sent to a low-pass filter for synthesis 51 and a high-pass filter for synthesis 52, associated with the low-pass filter for analysis 11 and the high-pass filter for analysis 12, respectively. The low-pass filter for synthesis 51 and the high-pass filter for synthesis 52 interpolate the output data strings of the upsampling units 41, 42. The data strings XL[i], XH[i] of the respective frequency bands are summed together by an adder 6 (specifically an adder summing two data strings together) in order to restore the input signal x[i] as the synthesis output signal X"[i].
The low-pass filter for analysis 11 and the high-pass filter for analysis 12 on the side of the wavelet transform unit 2 and the low-pass filter for synthesis 51 and the high-pass filter for synthesis 52 on the side of the inverse wavelet transform unit 4 are configured for completely or approximately satisfying the relation of the following equations (5) and (6): EQU H0(-z)F0(z)+H1(-z)F1(z)=0 (5) EQU H0(z)F0(z)+H1(z)F1(z)=2z-L . . . (6)
In the above equations (5) and (6), H0(z), H1(z), F0(z) and F1(z) are transfer functions of the low-pass filter for analysis 11, high-pass filter for analysis 12, low-pass filter for synthesis 51 and the high-pass filter for synthesis 52, respectively, L being an optional integer. By these constraint conditions, it can be assured that, if the input data is infinitely long, the output signal X"[i] of the adder 6 in the inverse wavelet transform unit 4 can completely or approximately coincide with the input signal x[i]. FIG. 22 shows an example of filter coefficients of the low-pass filter for analysis 11, high-pass filter for analysis 12, low-pass filter for synthesis 51 and the high-pass filter for synthesis 52, associated with one another.
If the above-mentioned wavelet splitting/synthesis is used for encoding, encoding/decoding is carried out between the downsampling units 21, 22 and the upsampling units 41, 42 of FIG. 21.
FIGS. 23 and 24 show a conventional structure of an encoding device and a decoding device for a one-dimensional data string employing wavelet transform.
In an encoding device 60, shown in FIG. 23, an input signal x[i] at an input terminal 61 is band-split by a low-pass filter for analysis 62 and a high-pass filter for analysis 63 into a data string XL0[i] of the low frequency band and a data string XH0[i] of the high frequency band. The data string XL0[i] of the low frequency band and the data string XH0[i] of the high frequency band are sent to associated downsampling units 64, 65 for sub-sampling as indicated by the equation (1).
The data string XL0[i] of the low frequency band, sub-sampled by the downsampling unit 64, is further band-split by a low-pass filter for analysis 66 and a high-pass filter for analysis 67. The data string, outputted by the low-pass filter for analysis 66, and the data string, outputted by the high-pass filter for analysis 67, are termed a data string XL1[i] of the low frequency band and a data string XH1[i] of the intermediate frequency band, respectively. The data string XL1[i] of the low frequency band and the data string XH1[j] of the intermediate frequency band are down-sampled by associated quantizers 71, 72, respectively.
On the other hand, the data string XH0[i] of the high frequency band, passed through the high-pass filter for synthesis 63, is down-sampled by a downsampling unit 65. The data string XH0[i] of the high frequency band, resulting from downsampling by the downsampling unit 65, is sent to a delay unit 70 for synchronization with the data string XL1[k] of the low frequency band and a data string XH1[k] of the intermediate frequency band.
The data string XH0[j] of the high frequency band, delayed by the delay unit 70 for synchronization, and the data string XL1[k] of the low frequency band and the data string XH1[k] of the intermediate frequency band, downsampled by second-stage downsampling units 68, 69, respectively, are entered to the associated quantizers 71, 72, 73 so as to be thereby quantized as shown by the equations (7), (8) and (9): EQU XL1'[k]XL1[k]/QL1 (7) EQU XH1'[k]XH1[k]/QH1 (8) EQU XH0'[i]=XH0[j]/QH0 (9)
employing associated quantization steps QH0, QH1, QL1, respectively. In these equations, rounding of the subdecimal number is by half-adjustment.
The data strings XL1'[k], XH1'[k] and XH0'[j], quantized by the quantizers 71, 72, 73, are entered to a reversible encoder/multiplexer 74 so as to be thereby compressed in a loss-free manner using adaptive arithmetic encoding. The resulting data strings are further multiplexed and outputted at an output terminal 75. The output signal to which an error correction code is appended is modulated so as to be recorded on a storage medium or transmitted over a transmission channel.
The data strings, subsequently reproduced from the storage medium and transmitted over the transmission channel, are demodulated and corrected for errors so as to be sent to a decoding device 80 shown in FIG. 24.
The arithmetic encoding is explained briefly. In the arithmetic encoding, a domain [0, 1) is split in proportion to the probability of occurrence of each symbol, where "[" means including values on the boundary and ")" means excluding values on the boundary, so that the above band corresponds to a domain of presence of x satisfying 0.ltoreq.x.ltoreq.1. The operation of associating the symbols being encoded to this partial domain is repeated recursively for a series of symbols. The decimal portion of a coordinate of a point comprised in the resulting domain, represented by binary sub-zero portion that can at least be demarcated from other domains, is used as a code. In the adaptive arithmetic encoding for input data, the probability of occurrence of each symbol is corrected each time data is entered. For monitoring the probability of occurrence of each symbol, a histogram representing the frequency of occurrence of each symbol is used. In executing the operation on the histogram, it is necessary to pre-set the maximum size that can be assumed by a symbol (this maximum value is hereinafter referred to as an alphabetical size). For this value, a value common to the encoding device and the decoding device is assumed to be set. Should there occur a symbol larger than the alphabetical size set on the encoding device side, it is replaced by the alphabetical size for encoding.
In a decoding device 80, shown in FIG. 24, signals are sent from a storage medium or over a transmission channel to an input terminal 81 and thence to a demultiplexer/reversible decoder 82. This demultiplexer/reversible decoder 82 performs demultiplexing and decoding, as inverse operations of the multiplexing and reversible encoding by the reversible encoder/multiplexer 74 of an encoding device 60, in order to restore data strings XL1'[k], XH1'[k] and XH0?[j]. These data strings are entered to associated dequantizers 83, 84, 85 where the data strings are dequantized, by way of reverse operations from the quantizers 71 to 73, in accordance with the following equations (10) to (12) EQU XL1"[k]=XL1'[k]X QL1 (10) EQU XH1[k]XH1'[k]X QH1 (11) EQU XH0"[j]=XH0'[j]X QH0 (12)
using respective different quantization steps QH0, QH1, QL1, in order to find data strings XL1"[k], XH1"[k] and XH0"[j].
The data string XL1"[k] of the low frequency band and the data string XH1"[k] of the intermediate band are entered to associated upsampling units 86, 87, respectively. The data string XL1"[j] of the low frequency band and the data string XH1"[j] of the intermediate band, upsampled in a manner as in the equations (3) and (4), are sent to associated synthesis filters, that is a second low-pass filter for analysis 88 and a second high-pass filter for analysis 89. The low-pass filter for synthesis 88 and the second high-pass filter for synthesis 89 are related with the low-pass filter for analysis 66 and the high-pass filter for analysis 67 as shown by the equations (5) and (6). Output data strings of the low-pass filter for synthesis 88 and the second high-pass filter for synthesis 89 are summed in an adder 90 and entered as a data string XL0"[j] to an upsampling unit 92. This data string XL0"[j] is associated with the data string XL0[j] of the low frequency band obtained by first-stage splitting in the encoding device 60.
On the other hand, the data string XH0"[j] of the high frequency band is also entered to the upsampling unit 93. The data string XH0"[j] is entered to a delay unit 91 for synchronization with the data string XH1"[j] of the intermediate frequency band and the data string XL1"[j] of the low frequency band via the low-pass filter for synthesis 88, high-pass filter for synthesis 89 and via the adder 90, that is for providing a delay necessary for re-construction of the output data string XL0"[j] from the adder 90.
The data string XH0"[j] of the high frequency band, delayed by the delay unit 91, and the output data string XL0"[j] from the adder 90, are upsampled by associated upsampling units 92, 93, respectively. The resulting data strings, that is the data string XL0"[i] of the low frequency band and the data string XH0"[i] of the high frequency band are respectively entered to a low-pass filter for synthesis 94 and to a high-pass filter for synthesis 95, associated respectively with the low-pass filter for analysis 66 and the high-pass filter for analysis 67 of the encoding device 60. Output data strings of the low-pass filter for synthesis 94 and the high-pass filter for synthesis 95, are summed together by an adder 96 so as to be outputted at an output terminal 97 as a regenerated signal X"[8 i] associate with the input signal x[i] of the encoding device 60.
Although the same combination of the low-pass filter for analysis, high-pass filter for analysis, low-pass filter for synthesis and the high-pass filter for synthesis is used in the above embodiment for all splitting levels, it is also possible to use different combinations form level to level.
FIGS. 25 and 26 show structures of conventional examples of the two-dimensional picture encoding and decoding devices employing wavelet transform. Specifically, FIG. 25 shows the structure of an encoding device 100 and FIG. 26 shows the structure of a decoding device 150.
The basic structure of the two-dimensional picture encoding device, employing wavelet transform unit, as shown in FIG. 25, is the same as the structure of FIG. 23 described above. However, the input data at this time is a data string obtained on scanning the two-dimensional picture in the sequence shown in FIG. 27. Also, in the present illustrative structure, in order to effect band splitting in both the horizontal and vertical directions on the picture, four filtering operations, namely the low-pass filtering and high-pass filtering in the horizontal direction and those in the vertical direction, are carried out in each stage of splitting in the encoding device 100 of FIG. 25.
Referring first to FIG. 25, the encoding device 100 splits the input signal x[i] entered at an input terminal 101 by a horizontal low-pass filter for analysis 102 and a horizontal high-pass filter for analysis 103, as analysis filters, into a data string in the low frequency band and a data string in the high frequency band in the horizontal direction. In the following description, the output data string from the horizontal low-pass filter for analysis 102 and that from the horizontal high-pass filter for analysis 103 are termed a data string of the first band and a data string of a second band, respectively.
These data strings of the first and second data strings are downsampled by associated downsampling units 104, 105, respectively. These data strings of the first and second data strings, downsampled by associated downsampling units 104, 105, are stored in associated memories 106, 107, respectively.
The data string of the first band, read out from the memory 106, is band-split in the vertical direction by a vertical low-pass filter for analysis 108 and a vertical high-pass filter for analysis 109 in the vertical direction. Similarly, the data string of the second band, read out from the memory 107, is band-split in the vertical direction by a vertical high-pass filter for analysis 108 and a vertical high-pass filter for analysis 111. The memories 106, 107 are line memories for temporarily storing a number of line data required for vertical band splitting by the downstream side vertical low-pass filter for analysis 108, vertical high-pass filter for analysis 109, vertical low-pass filter for analysis 110 and vertical high-pass filter for analysis 111. In the following description, the output data string from the vertical low-pass filter for analysis 108 is termed a data string of the third band, the data string downstream of the vertical high-pass filter for analysis 109 is termed a data string of the fourth band, the data string downstream of the vertical low-pass filter for analysis 110 is termed a data string of the fifth band and the data string downstream of the vertical high-pass filter for analysis 110 is termed a data string of the sixth band.
The data strings of the third to sixth data strings are further down-sampled by the associated downsampling units 112, 113, 114 and 115, respectively.
The data string of the lowest third band, taken out by the vertical low-pass filter for analysis 108 and downsampled by the downsampling unit 112, is further band-split in the horizontal direction by a horizontal low-pass filter for analysis 116 and a horizontal high-pass filter for analysis 117. In the following description, an output data stream from the horizontal low-pass filter for analysis 116 is termed a data string of a seventh band and an output data stream from the horizontal high-pass filter for analysis 117 is termed a data string of an eighth band.
The data strings of the seventh and eighth bands from the horizontal low-pass filter for analysis 116 and the horizontal high-pass filter for analysis 117 are further downsampled by downsampling units 118, 119 so as to be stored in memories 120, 121.
The data string of the seventh band, read out from the memory 120, is further band-split in the vertical direction by a vertical low-pass filter for analysis 122 and a vertical high-pass filter for analysis 123. Similarly, the data string of the eighth band, read out from the memory 121, is further band-split in the vertical direction by a vertical low-pass filter for analysis 124 and a vertical high-pass filter for analysis 125. Thus, the memories 118, 119 are line memories for temporarily storing a number of line data required for vertical band splitting by the downstream side filters 122 to 125. In the following description, the output data string downstream of the vertical low-pass filter for analysis 122 is termed a data string of the ninth band, the data string downstream of the vertical high-pass filter for analysis 123 is termed a data string of the tenth band, the data string downstream of the vertical low-pass filter for analysis 124 is termed a data string of the eleventh band and the data string downstream of the vertical high-pass filter for analysis 125 is termed a data string of the twelfth band.
The data strings of the ninth to twelfth bands are further downsampled by associated downsampling units 126, 127, 128, 129 so as to be sent to associated quantizers 133, 134, 135, 136.
The fourth, fifth and sixth data strings from the downsampling units 113, 114, 115 are entered to delay units 130, 131, 132 for synchronization with the data strings of the ninth to twelfth bands.
The data strings of the fourth to sixth bands, delayed (synchronized) by these delay units 130 to 132, and those of the ninth to twelfth bands from the downsampling units 126 to 129, are sent to associated quantizers 133 to 139, respectively, so as to be quantized by these associated quantizers 133 to 139, using respective different quantization steps.
The respective data strings, quantized by these quantizers 133 to 139, are entered to a reversible encoder/multiplexer 140 so as to be thereby processed with loss-free compression using adaptive arithmetic encoding. The compressed data strings are further multiplexed and outputted at an output terminal 41. To the output signals, error correction codes are further appended, and the resulting signals are modulated for storage on a storage medium or transmission over a transmission channel.
The signals reproduced from the storage medium or transmitted over the transmission channel are demodulated and corrected for errors before being sent to a decoding device 150 shown in FIG. 26.
The signals from the storage medium or over the transmission channel are entered to an input terminal 151 of the decoding device 150 shown in FIG. 26 and thence sent to a demultiplexer/reversible decoder 152. The demultiplexer/reversible decoder 152 performs reverse operations of the multiplexing and reversible encoding applied by the reversible encoder/multiplexer 140 of the encoding device 100 for restoring data strings associated with data strings of the fourth to sixth bands and the ninth to twelfth bands. These data strings are entered to associated dequantizers 153 to 159 so as to be dequantized using respective different quantization steps.
Output data strings of the dequantizers 153 to 159 are sent via associated memories 161 to 164 to upsampling units 165 to 168, respectively, for upsampling. The upsampled data strings are interpolated in the vertical direction by a vertical low-pass filter for synthesis 169, vertical high-pass filter for synthesis 170, a vertical low-pass filter for synthesis 171 and a vertical high-pass filter for synthesis 172, for interpolation in the vertical direction.
Thus, the memories 161 to 164 are line memories for temporarily storing a number of line data required for vertical interpolation by the downstream side synthesis filters 169 to 172.
Output data strings of the vertical low-pass filter for synthesis 169 and the vertical high-pass filter for synthesis 170 are summed together by an adder 173, while output data strings of the vertical low-pass filter for synthesis 171 and the vertical high-pass filter for synthesis 172 are summed together by an adder 174.
Output data strings of the adders 173, 174 are upsampled by associated upsampling units 175, 176 and subsequently interpolated in the horizontal direction by a horizontal low-pass filter for synthesis 177 and a horizontal high-pass filter for synthesis 178, respectively. Output data strings of the horizontal low-pass filter for synthesis 177 and the horizontal high-pass filter for synthesis 178 are summed together by an adder 179 so as to be stored in a memory 183. The data string read out from the memory 183 is upsampled by an upsampling unit 187 and subsequently interpolated in the vertical direction by a vertical low-pass filter for synthesis 191. Thus, the memory 183 is a line memory for temporarily storing a number of line data required for vertical interpolation by the downstream side synthesis filter 191.
On the other hand, output data strings of the dequantizers 157 to 159 are fed via associated memories 184 to 186 and upsampled by upsampling units 188, 189 so as to be interpolated in the vertical direction by a vertical high-pass filter for synthesis 192, a vertical low-pass filter for synthesis 193 and a vertical high-pass filter for synthesis 194. Meanwhile, the data strings sent to the vertical high-pass filter for synthesis 192, vertical low-pass filter for synthesis 193 and to the vertical high-pass filter for synthesis 194, are previously delayed by delaying units 180 to 182 for synchronization between the interpolation by the filters 192 to 194 and the interpolation by the vertical low-pass filter for synthesis 191.
The data string from the vertical low-pass filter for synthesis 191 and the data string from the vertical high-pass filter for synthesis 192 are summed together by an adder 195, while the data string from the vertical low-pass filter for synthesis 193 and the data string from the vertical high-pass filter for synthesis 194 are suited together by an adder 196. These data strings from the adders 195 and 196 are upsampled by associated upsampling units 197, 198 and interpolated in the horizontal direction by a horizontal low-pass filter 199 and a horizontal high-pass filter 200 so as to be then summed together by a adder 201 to regenerate a data string. The regenerated data string is approximately the same data as the input data stream of the encoding device 100 of FIG. 25 and is outputted at an output terminal 202.
In the configuration shown in FIGS. 25 and 26, the downsampling units 112 to 115 and 126 to 129 in the encoding device 100 perform downsampling in the vertical direction, that is line-based decimation, on the picture. Conversely, the upsampling units 165 to 168 and 187 to 190 in the vertical direction in the decoding device 150 perform processing of inserting an all-zero line between input neighboring lines.
Although the same filters are used in the horizontal and vertical directions, it is similarly possible to use different filter sets in the respective directions.
In the conventional encoding or decoding apparatus employing wavelet transform/inverse wavelet transform, as described above, wavelet filters used are previously set, in a majority of cases, such that filters cannot be switched responsive to pictures or to computational ability of the apparatus.
Also, the information as to a proper folding method at the terminal portion of a data string, which differs with different wavelet filters used, cannot be transmitted to the decoding device, or is not used properly on the decoding device, such that correct folding is not achieved to deteriorate the picture quality.
In addition, the optimum initial setting of the histograms, used for monitoring the probability of occurrence of respective symbols required in decoding, such as wavelet coefficients, in adaptive arithmetic encoding, may differ with bitrates or with input pictures, even although the histograms are initially set so as to be equal for all symbols.
Moreover, there is raised a problem that the magnitude of the quantized wavelet coefficients are varied with the quantization steps used, even although the maximum size (alphabetical size) that can be assumed by a symbol is set to a common value for the encoding device and the decoding device and cannot be changed, such that coefficients larger than the pre-set alphabetical size are clipped thus occasionally deteriorating the picture quality.
Furthermore, there is raised a problem that, if the pre-set alphabetical size is larger than the maximum magnitude of the actually occurring symbol, the arithmetic encoding is lowered in compression efficiency.
The present invention has been proposed for overcoming the above-described problem. It is an object of the present invention to provide an encoding method and apparatus, a decoding method and apparatus and a recording medium whereby the filters can be switched depending on the picture or on the possible computational ability of the apparatus and whereby optimum initial setting can be achieved depending on an input picture or bitrate to realize optimum picture quality.